//simplify3 is new edition of simplify[|2],
//it allows you to operate with multiple outlines: each node is elimineated or leaved in all the outline,
//simplify is leaved intact because it's well tested and commented

//simplification is elimination of contour's nodes
#pragma once

#include "outline.h"

namespace outline {

template <typename E>
class simplifier
{
public:
	typedef E estimator_type;
	typedef typename E::sample	sample;
	typedef std::vector<sample>	sample_vector;
	typedef std::vector<sample_vector> some_sample_vectors;
	struct patch : E::patch {
		size_t istart;
	};
	typedef std::vector<patch>	patch_vector;
	typedef std::vector<patch_vector> some_patch_vectors;
public:
	E estimator;
public:
	// all the following methods return
	// measure (sum of squares) of discrepancy between nodes of source outline(s) and simplified outline(s).
	// In pairs of methods one is responsible for simplification of single outline,
	// while the other --- for multiple of outlines.

	double simplify_min_step_len(int min_step_len, 
		sample_vector const & src, patch_vector & dst);
	double simplify_many_min_step_len(int min_step_len,
		some_sample_vectors const & src, some_patch_vectors & dst);

	///exactly K nodes in contour is leaved
	double simplify_to_K_nodes(int K,
		sample_vector const & src, patch_vector & dst);
	double simplify_many_avg_step_len(float avg_step_len,
		some_sample_vectors const & src, some_patch_vectors & dst);

	/// minimal number of nodes is leaved providing error less than given argument
	double simplify_max_discrepancy(double max_discrepancy,
		sample_vector const & src, patch_vector & dst);
	/// avg_discrepancy is the total discrepancy divided by node count in source contours
	double simplify_many_avg_discrepancy(double avg_discrepancy,
		some_sample_vectors const & src, some_patch_vectors & dst);

public:
	/// copies only those samples where patches begin or end
	void skeleton(sample_vector const & src, 
		patch_vector const & patches, sample_vector & dst)
	{
		dst.clear();
		dst.reserve(patches.size() + 1);
		for (size_t i = 0; i < patches.size(); ++i)
			dst.push_back(src[patches[i].istart]);
		if (patches[0].istart == 0)
			dst[patches.size()] = src.back(); //good both for closed and open contours
		else
			dst[patches.size()] = src[patches[0].istart];
	}

private:
	/// here[i] describes what would be if simplified outline node 
	/// coinsides with i'th source outline node
	struct here {
		double d; ///< discrepancy (-1, if no node is possible here)
		patch p; ///< best previous patch (p.istart points on best previous node in simplified outline)
	public:
		here() { }
		here(double dd, patch const & pp) : d(dd), p(pp) { }
	};
	typedef std::vector<here> here_vector;

private:
	double simplify_min_step_len_core(int min_step_len, 
		sample_vector const & src, patch_vector & dst, bool closed);
	double simplify_to_K_nodes_core(int K,
		sample_vector const & src, patch_vector & dst, bool closed);
	double simplify_max_discrepancy_core(double max_discrepancy,
		sample_vector const & src, patch_vector & dst, bool closed);
private:
	void make_first_layer(sample_vector const & src, here_vector & first);
	void make_next_layer(sample_vector const & src,
		here_vector const & last, here_vector & next);
	void layers_back_pass(
		std::vector<here_vector> const & layers, int last_step,
		patch_vector & reverse);
	void back_shift(patch_vector & dst, int s, int outline_size);
};

} //namespace outline
